`:top

Das `!Rucksackproblem`! (auch `F33f`_`[englisch`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Englische_Sprache]`_`f `*knapsack problem`*) ist ein `F33f`_`[Optimierungsproblem`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Optimierungsproblem]`_`f der `F33f`_`[Kombinatorik`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Kombinatorik]`_`f. Aus einer Menge von Objekten, die jeweils ein Gewicht und einen `F33f`_`[Nutzwert`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Nutzwert]`_`f haben, soll eine `F33f`_`[Teilmenge`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Teilmenge]`_`f ausgewählt werden, deren Gesamtgewicht eine vorgegebene Gewichtsschranke nicht überschreitet. Unter dieser Bedingung soll der Nutzwert der ausgewählten Objekte maximiert werden.

Die Entscheidungsvariante des Rucksackproblems fragt, ob ein zusätzlich vorgegebener Nutzwert erreicht werden kann. Sie gehört zur Liste der `F33f`_`[21 klassischen NP-vollständigen Probleme`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Karps_21_NP-vollständige_Probleme]`_`f, von denen `F33f`_`[Richard Karp`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Richard_M._Karp]`_`f 1972 die Zugehörigkeit zu dieser Klasse zeigen konnte.`:cite-ref-1[`F5bf`_`[1`#cite-note-1]`_`f]

In der `F33f`_`[Kryptographie`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Kryptographie]`_`f wird häufig eine andere Entscheidungsvariante betrachtet. Dabei werden nur die Gewichte betrachtet und es wird gefragt, ob es eine Teilmenge der Objekte gibt, die einen vorgegebenen Gewichtswert genau erreicht. Diese Problemvariante wird auch als `F33f`_`[SUBSET-SUM`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Subset_Sum]`_`f bezeichnet. Basierend auf dieser Variante wurde das Public-Key-Kryptoverfahren `F33f`_`[Merkle-Hellman-Kryptosystem`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Merkle-Hellman-Kryptosystem]`_`f entwickelt, das sich allerdings als nicht besonders sicher herausstellte.

>>Contents

• `F0af`_`[Anschauung`#anschauung]`_`f

• `F0af`_`[Mathematische Formulierung`#mathematische-formulierung]`_`f

• `F0af`_`[Lösung durch dynamische Programmierung`#l-sung-durch-dynamische-programmierung]`_`f

• `F0af`_`[Lösung mittels Profitabilitätsindex`#l-sung-mittels-profitabilit-tsindex]`_`f

• `F0af`_`[Lösung mittels ganzzahliger linearer Optimierung`#l-sung-mittels-ganzzahliger-linearer-optimierung]`_`f

• `F0af`_`[Anwendungen`#anwendungen]`_`f

• `F0af`_`[Siehe auch`#siehe-auch]`_`f

• `F0af`_`[Literatur`#literatur]`_`f

• `F0af`_`[Weblinks`#weblinks]`_`f

• `F0af`_`[Einzelnachweise`#einzelnachweise]`_`f

-─

>>Anschauung

Das Rucksackproblem hat seinen Namen aus folgender Anschauung heraus erhalten: Es sind verschiedene Gegenstände mit einem bestimmten Gewicht und einem Nutzwert gegeben. Aus diesen Gegenständen soll nun eine Auswahl getroffen werden, die in einen Rucksack mit einer vorgegebenen Gewichtsschranke mitgenommen werden können. In der Literatur wird zur Veranschaulichung auch gerne der Dieb herangezogen, der nur einen kleinen Teil der Beute im Rucksack abtransportieren kann und nun versucht, das Maximum an Nutzwert herauszuschlagen.

>>Mathematische Formulierung

Gegeben ist eine `F33f`_`[endliche Menge`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Endliche_Menge]`_`f von Objekten U {\\displaystyle U} . Durch eine Gewichtsfunktion w {\\displaystyle w} und die Nutzenfunktion v {\\displaystyle v} wird den Objekten ein Gewicht und ein festgelegter Nutzwert zugeordnet:

w : : U → → R {\\displaystyle w\\colon U\\rightarrow \\mathbb {R} }

v : : U → → R {\\displaystyle v\\colon U\\rightarrow \\mathbb {R} }

Des Weiteren gibt es eine vorgegebene Gewichtsschranke B ∈ ∈ R {\\displaystyle B\\in \\mathbb {R} } .

Gesucht ist eine Teilmenge K ⊆ ⊆ U {\\displaystyle K\\subseteq U} , die die Bedingung

∑ ∑ u ∈ ∈ K w ( u ) ≤ ≤ B {\\displaystyle \\sum _{u\\in K}w(u)\\leq B} einhält und die Zielfunktion ∑ ∑ u ∈ ∈ K v ( u ) {\\displaystyle \\sum _{u\\in K}v(u)} maximiert.

Der Spezialfall v = w {\\displaystyle v=w} führt auf das `F33f`_`[Teilsummenproblem`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Teilsummenproblem]`_`f.

>>Lösung durch dynamische Programmierung

Sind die Gewichte ganzzahlig, so lässt sich der optimale Wert des Rucksackproblems auch mittels `F33f`_`[dynamischer Programmierung`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Dynamische_Programmierung]`_`f lösen. Seien dazu 1 , … … , n {\\displaystyle 1,\\ldots ,n} die Elemente von U {\\displaystyle U} .

`B100`F9d9Eingabe: U, B, w, v wie oben beschrieben`f`b

`B100`F9d9 R := [1…(n+1), 0…B]-Matrix, mit Einträgen 0`f`b

`B100`F9d9 FOR i = n … 1`f`b

`B100`F9d9 FOR j = 1 … B`f`b

`B100`F9d9 IF w(i) <= j`f`b

`B100`F9d9 R[i,j] := max( v(i) + R[i+1, j-w(i)], R[i+1,j] )`f`b

`B100`F9d9 ELSE`f`b

`B100`F9d9 R[i,j] := R[i+1,j]`f`b

`B100`F9d9Ausgabe: R[1,B]`f`b

In jeder Speicherzelle R ( i , j ) {\\displaystyle R(i,j)} ist der maximale Nutzwert bei maximal möglichem Gesamtgewicht von j {\\displaystyle j} bei Berücksichtigung einer Teilmenge von Gegenständen aus der Teilsequenz [ i . . n ] {\\displaystyle [i..n]} der Gesamtsequenz aller Gegenstände [ 1.. n ] {\\displaystyle [1..n]} . Also ist der maximale Nutzwert bei Berücksichtigung einer Teilmenge aller Gegenstände in der Zelle R ( 1 , B ) {\\displaystyle R(1,B)} nach Beendigung des Algorithmus gespeichert.

In jeder Zeile i {\\displaystyle i} der Matrix R {\\displaystyle R} wird über die beiden Fälle optimiert, ob der Nutzwert maximal vergrößert werden kann, wenn der Gegenstand i {\\displaystyle i} mit dem Gewicht w ( i ) {\\displaystyle w(i)} dem Rucksack hinzugefügt oder er nicht aufgenommen wird. Im ersten Fall erhöht sich der Nutzwert um v ( i ) {\\displaystyle v(i)} .

Um den Inhalt des Rucksacks mit dem maximalen Nutzwert zu bestimmen, kann er rekonstruiert werden, indem die Berechnung des Optimums in R ( 1 , B ) {\\displaystyle R(1,B)} mittels `F33f`_`[Backtracking`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Backtracking]`_`f zurückverfolgt wird.

Die Korrektheit folgt aus der folgenden Beobachtung:

Sei K ⋆ ⋆ {\\displaystyle K^{\\star }} eine optimale Lösung. Dann ist K ⋆ ⋆ ∖ ∖ { i } {\\displaystyle K^{\\star }\\backslash \\{i\\}} eine optimale Lösung für die Instanz U ∖ ∖ { i } {\\displaystyle U\\backslash \\{i\\}} mit Maximalgewicht B − − w ( i ) {\\displaystyle B-w(i)} . Der Algorithmus benötigt aufgrund der verschachtelten `F33f`_`[for-Schleifen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=For-Schleife]`_`f, die über n und B iterieren, eine Laufzeit von O ( n ⋅ ⋅ B ) {\\displaystyle O(n\\cdot B)} . Hierbei ist zu beachten, dass `*B`* eine zu seiner Eingabelänge exponentiell wachsende Größe und somit die Laufzeit `F33f`_`[pseudopolynomiell`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Pseudopolynomiell]`_`f ist.

>>Lösung mittels Profitabilitätsindex

In der Praxis wird ein Ranking der Objekte nach Profitabilitätsindex vorgenommen:

P I = W ÷ ÷ R {\\displaystyle PI=W\\div R}

• PI = Profitabilitätsindex

• W = Generierter Wert (hier: Nutzwert)

• R = Verbrauchte Ressourcen (hier: Gewicht)

Dann werden möglichst viele Objekte gewählt, beginnend mit dem Objekt mit höchstem Profitabilitätsindex. Dies führt bei ganzzahligen Problemen nicht immer zur optimalen Lösung, ist aber sehr praktikabel. Bei dieser Methodik handelt es sich um einen `F33f`_`[Greedy-Algorithmus`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Greedy-Algorithmus]`_`f.

>>Lösung mittels ganzzahliger linearer Optimierung

Das Rucksackproblem lässt sich wie folgt als `F33f`_`[ganzzahliges lineares Optimierungsproblem`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Ganzzahlige_lineare_Optimierung]`_`f (`*integer linear program`* oder kurz `*ILP)`* formulieren. Sei dazu y u ∈ ∈ { 0 , 1 } {\\displaystyle y_{u}\\in \\{0,1\\}} für jedes Element u ∈ ∈ U {\\displaystyle u\\in U} eine binäre Entscheidungsvariable mit der folgenden Interpretation:

• y u = 1 {\\displaystyle y_{u}=1} : Das Element u {\\displaystyle u} wird im Rucksack mitgenommen.

• y u = 0 {\\displaystyle y_{u}=0} : Das Element u {\\displaystyle u} wird nicht im Rucksack mitgenommen.

Dies führt zu folgender Modellierung des Rucksackproblems

I L P : max y ∑ ∑ u ∈ ∈ U v ( u ) y u s. t. ∑ ∑ u ∈ ∈ U w ( u ) y u ≤ ≤ B , y u ∈ ∈ { 0 , 1 } , u ∈ ∈ U {\\displaystyle ILP:\\qquad \\max _{y}\\sum _{u\\in U}v(u)y_{u}\\quad {\\text{s. t.}}\\quad \\sum _{u\\in U}w(u)y_{u}\\leq B,\\ y_{u}\\in \\{0,1\\},\\ u\\in U} ,

welches mit gängigen kommerziellen und nichtkommerziellen Solvern wie etwa `F33f`_`[CPLEX`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=CPLEX]`_`f, `F33f`_`[Gurobi`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Gurobi]`_`f, FICO Xpress, SCIP, `F33f`_`[GLPK`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=GLPK]`_`f und CBC auch für große praxisrelevante Instanzen global optimal gelöst werden kann.`:cite-ref-2[`F5bf`_`[2`#cite-note-2]`_`f]

>>Anwendungen

Viele reale Situationen lassen sich mit Hilfe der Lösung dieses Problems mathematisch klären. Oft steht eine begrenzte Kapazität zur Verfügung, welche nicht die gesamte Nachfrage befriedigen kann. Man denke z. B. an einen Lkw, der viele verschiedene Güter – mit einem bestimmten Gewinn – transportieren soll, aber wegen der begrenzten Lademenge nicht alle Güter aufnehmen kann. Der Besitzer des Lkws wird die Ladung so wählen wollen, dass der Gewinn maximal ausfällt.

>>Siehe auch

• `F33f`_`[Greedy-Algorithmus`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Greedy-Algorithmus]`_`f

• `F33f`_`[Optimierungsproblem`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Optimierungsproblem]`_`f

• `F33f`_`[Teilsummenproblem`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Teilsummenproblem]`_`f

• `F33f`_`[Partitionsproblem`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Partitionsproblem]`_`f

>>Literatur

• `F33f`_`[Hans Kellerer`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Hans_Kellerer]`_`f, Ulrich Pferschy, David Pisinger: Knapsack Problems. Springer, Berlin u. a. 2004, ISBN 3-540-40286-1.

• Silvano Martello, Paolo Toth: Knapsack problems. Algorithms and computer implementations. J. Wiley, Chichester u. a. 1990, ISBN 0-471-92420-2 (Buch als PDF und Fortran-Quelltext zum Buch).

>>Weblinks

• Das Rucksackproblem (Knapsack Problem) – Ausführliche Erklärung mit Grafiken und Beispiel-Implementierung

>>Einzelnachweise

`:cite-note-1`!1.`! `F0af`_`[↑`#cite-ref-1]`_`f Richard M.Karp: Reducibility Among Combinatorial Problems. In: Springer (Hrsg.): Proceedings of a symposium on the Complexity of Computer Computations. Yorktown Heights, New York 1972, S. 85–103 (amerikanisches Englisch, springer.com).

`:cite-note-2`!2.`! `F0af`_`[↑`#cite-ref-2]`_`f David Pisinger: Where are the hard knapsack problems? In: Computers & Operations Research. Band 32, Nr. 9, September 2005, `F33f`_`[ISSN`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Internationale_Standardnummer_für_fortlaufende_Sammelwerke]`_`f 0305-0548, S. 2271–2284, `F33f`_`[doi`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Digital_Object_Identifier]`_`f:10.1016/j.cor.2004.03.002 (englisch, gla.ac.uk [PDF; abgerufen am 4. Dezember 2023]).

`c`F0af`_`[↑ Back to top`#top]`_`f`a